The present invention relates to detection of motion vectors between two images, and, more particularly, is directed to efficient detection of motion vectors.
An example of a system in which motion vector detection is useful is a system according to the Moving Picture Coding Experts Group (MPEG) standard, which is concerned with high efficiency compression coding of a moving image. In the MPEG standard, an image is encoded using discrete cosine transformation (DCT) and predictive encoding with motion compensation. Motion vectors are used during motion compensation.
FIG. 1 shows an example of an apparatus according to the MPEG standard. Image data, also referred to as pixel data, is supplied to an input terminal 201, which applies the image data to a motion vector detecting circuit 202 and to a subtracting circuit 203.
The motion vector detecting circuit 202 produces motion vectors for a present frame relative to a reference frame, and supplies these motion vectors to a motion compensating circuit 204 which applies the motion vectors to the reference frame stored in frame memory 205 to generate motion compensated image data. That is, the circuit 204 performs motion compensation on the reference frame read from frame memory 205 using the motion vectors from circuit 202. The circuit 204 supplies the motion compensated image data to the subtracting circuit 203 and to an adding circuit 206.
The subtracting circuit 203 functions to subtract the motion compensated image data of the reference frame from the image data of the present frame supplied from input terminal 201 to produce difference data, and to supply the difference data to a DCT circuit 207.
The DCT circuit 207 operates to transform the difference data to produce coefficient data, and to supply the coefficient data to a quantizer 208 which functions to quantize the coefficient data and to supply quantized data to an output terminal 209 and to an inverse quantizer 210.
The inverse quantizer 210 dequantizes the quantized data supplied thereto to produce recovered coefficient data, and applies the recovered coefficient data to an inverse DCT circuit 211 which inverse transforms the recovered coefficient data to produce recovered difference data and supplies the recovered difference data to the adding circuit 206. The adding circuit 206 adds the motion compensated image data of the reference frame to the recovered difference data to produce predicted image data of the present frame and supplies the predicted present frame image data to the frame memory 205 which stores the predicted present frame image data as a next reference frame.
Three conventional methods for producing motion vectors are explained below. Generally, a portion or block of the present frame is selected, and the closest matching block from the reference frame is determined. A motion vector for the block of the present frame is the difference between the co-ordinates of the block of the present frame and the co-ordinates of the closest matching block of the reference frame. The motion vector detecting circuit 202 may use any of the three conventional methods which are referred to herein as a full search method, a multistep method and an interpolating method. The full search and multistep methods produce a motion vector having a resolution of one pixel. The interpolating method produces a motion vector having a resolution of better than one pixel.
The full search method of producing motion vectors will now be explained.
FIG. 2 shows a present frame 221 and a reference frame 222. Present frame 221 is shown as including a reference block 223. Reference frame 222 is shown as including a check block 224. The check block 224 is moved in a predetermined search range, and a degree of matching between the reference block 223 and the check block 224 is detected for each position of the check block 224 in the predetermined search range. A matching block is defined as the position where the check block has the best degree of matching to the reference block, and the motion vector for the reference block is set to indicate the matching block.
FIG. 3 shows an example of a conventional motion vector detecting apparatus which obtains motion vectors using the full search method. Image data of the present frame is supplied to an input terminal 233 which applies the present frame image data to a present frame memory 231. Image data of the reference frame is supplied to an input terminal 234 which applies the reference frame image data to a reference frame memory 232. Controller 235 controls reading and writing of the present and reference frame memories 231, 232.
Pixel data of the reference block of the present frame is read from the present frame memory 231. Pixel data of the check block of the reference frame is read from the reference frame memory 232. An address moving circuit 236 generates address data for reading the check block pixel data so that the check block moves, pixel by pixel, in the predetermined vector search range.
FIG. 4 shows a check block 241 being moved in the predetermined vector search range SV. Initially, the check block is positioned in the upper left corner of the search range, and a sum of differences is obtained, as explained below. Then, the check block is moved to the right by one pixel, and a sum of differences is obtained. The check block is again moved to the right by one pixel and a sum is obtained until it has reached the rightmost boundary of the search range. Then, the check block is positioned in the upper left corner of the search range, moved downward by one pixel, and a sum is obtained. The check block is moved to the right by one pixel and a sum is obtained at that position, until it has reached the rightmost boundary of the search range. Again, the check block is moved to the leftmost boundary, but downwards by two pixels from the upper left corner, and a sum is obtained. This procedure is repeated until the check block has been moved through the entire search range.
The reference block pixel data and the check block pixel data are supplied to a differential circuit 237 which subtracts these data and applies the resulting difference value to an absolute value summing circuit 238. The absolute value summing circuit 238 accumulates the difference values as a sum of absolute values of the difference values, for each of the pixel positions in the reference block, and supplies the sum to a judging circuit 239. That is, at each position of the check block in the predetermined search range SV, the summing circuit 238 obtains a sum of difference values.
The sum of differences may be represented by the following equation:                     E        =                              ∑                          i              =              1                                      M              xc3x97              N                                ⁢                      (                                          W                i                            xc3x97                              "LeftBracketingBar"                                                      A                    i                                    -                                      B                    i                                                  "RightBracketingBar"                                      )                                              (                  eq          .                      xe2x80x83                    ⁢          1                )            
where (Mxc3x97N) represents the size of each of the reference block and check block, Ai represents the pixels of the reference block, Bi represents the pixels of the check block, and Wi represents a weighting factor.
Alternatively, instead of the absolute value of the difference, the squared value of the difference could be used in equation 1.
The judging circuit 239 selects the check block position corresponding to the minimum sum of difference values as the matching block, calculates the motion vector between the reference block and the matching block, and supplies the motion vector to an output terminal 240.
Because the full search method proceeds by moving the check block on a pixel-by-pixel basis in the predetermined search range, a large amount of computation is required to obtain a motion vector using this method. However, this method always finds the best matching block in the predetermined search range.
The multistep method of producing motion vectors will now be explained.
The first step of the multistep method proceeds in the same manner as the full search method, except that the check block is moved by (i) pixels, i greater than 1, instead of by one pixel. Each succeeding step of the multistep method proceeds in the same manner as the full search method, with the resolution getting finer and the search range smaller and centered on the best matching block from the previous step, until in the last step of the multistep method, the check block is moved by one pixel through the final search range which is smaller than the original search range.
FIG. 5 shows an example of a conventional motion vector detecting apparatus which obtains motion vectors using the multistep method. Image data of the present frame is supplied to an input terminal 253 which applies the present frame image data to a present frame memory 251. Image data of the reference frame is supplied to an input terminal 254 which applies the reference frame image data to a reference frame memory 252. Controller 255 controls reading and writing of the present and reference frame memories 251, 252.
Pixel data of the reference block of the present frame is read from the present frame memory 251. Pixel data of the check block of the reference frame is read from the reference frame memory 252. An address moving circuit 256A generates address data for reading the check block pixel data so that the check block moves in a first step, for example, by two pixels at each readout, in the predetermined vector search range.
The reference block pixel data and the check block pixel data are supplied to a differential circuit 257 which subtracts these data and applies the resulting difference value to an absolute value summing circuit 258. The absolute value summing circuit 258 accumulates the difference values as a sum of absolute values of the difference values, for each of the pixel positions in the reference block, and supplies the sum to a judging circuit 259.
The judging circuit 259 selects the check block position corresponding to the minimum sum of difference values as the matching block for the first step, calculates a coarse motion vector between the reference block and the matching block.
Then, in the second step, check block pixel data is again read from the reference frame memory 254, but readout is controlled by address moving circuit 256B so that the check block moves pixel by pixel in a search range centered on the best matching block from the first step. The judging circuit 259 selects the check block position corresponding to the minimum sum of difference values as the matching block for the second step, calculates a fine motion vector between the reference block and the matching block, and supplies the fine motion vector to an output terminal 260.
FIG. 6 shows a check block 261 moved in the predetermined vector search range SV every (i) pixels (for example, two pixels). In the next step, the check block is moved every pixel at a location around such the best matching block from the first step. The multistep method may be used with three or more steps. For example, in a first step, the check block may be moved by four pixels, in a second step, the check block may be moved by two pixels and in a third step, the check block is moved by one pixel.
The multistep method requires fewer computations than the full search method, but may not find the best matching block in the predetermined search range. Specifically, when the coarse motion vector obtained in the first step is wrong, a correct motion vector cannot be obtained.
It has been proposed to, in the first step, enlarge a block of size (Nxc3x97M) to (2Nxc3x972M), subsample to produce a block of size (Nxc3x97M), and move the check block in the subsampled search range to obtain a coarse motion vector. However, this method is also not guaranteed to find the best motion vector in the original predetermined search range.
The interpolating method of producing motion vectors will now be explained.
The interpolating method proceeds in the same manner as the full search method, except that the pixels of the reference frame are interpolated, and the check block is moved at the interpolated resolution. For example, an interpolated pixel may be obtained between each pair of pixels in the search range of the reference frame, and the check block may be moved by one half of the original pixel resolution (one pixel of the interpolated resolution).
FIG. 7 shows an example of a conventional motion vector detecting apparatus which obtains motion vectors at a precision of better than one pixel using the interpolating method. Image data of the present frame is supplied to an input terminal 273 which applies the present frame image data to a present frame memory 271. Image data of the reference frame is supplied to an input terminal 274 which applies the reference frame image data to a reference frame memory 272. Controller 275 controls reading and writing of the present and reference frame memories 271, 272.
Pixel data of the reference block of the present frame is read from the present frame memory 271.
Data is read from the reference frame memory 272 and applied to an interpolating circuit 281 which interpolates adjacent readout pixels, also referred to as original pixels, to form interpolated pixels between the original pixels. The readout and interpolated pixel data form the pixel data of the check block.
FIG. 8 shows pixel data read from the memory 272 as filled-in circles ("Ovalsolid"). Interpolated data formed from two original pixels are shown as xe2x80x9cxxe2x80x9d (xc3x97). Interpolated data formed from four original pixels are shown as empty circles (◯). For example, interpolated pixel data Hxe2x88x921/2,0 is obtained as follows:
Hxe2x88x921/2,0=(Dxe2x88x921,0+D0,0)/2xe2x80x83xe2x80x83(eq. 2)
Interpolated pixel data Hxe2x88x921/2,xe2x88x921/2 is obtained as follows:
Hxe2x88x921/2,xe2x88x921/2=(Dxe2x88x921,xe2x88x921+D0,xe2x88x921+D0,0+Dxe2x88x921,0)/4xe2x80x83xe2x80x83(eq. 3)
The reference block pixel data and the check block pixel data are supplied to a differential circuit 277 which subtracts these data and applies the resulting difference value to an absolute value summing circuit 278. The absolute value summing circuit 278 accumulates the difference values as a sum of absolute values of the difference values, for each of the pixel positions in the reference block, and supplies the sum to a judging circuit 279.
The judging circuit 279 selects the check block position corresponding to the minimum sum of difference values as the matching block, calculates the motion vector between the reference block and the matching block, and supplies the motion vector to an output terminal 280. Since the check block included pixels interpolated half way between the reference frame pixels, the motion vector has a precision of one half pixel, that is, a resolution of better than one pixel.
The interpolating method produces a motion vector at a higher resolution than the full search method, but requires more computation than the full search method.
In each of the above-described methods for detecting motion vectors, the amount of computation required is large. Therefore, an apparatus using any of these methods requires a large amount of hardware, takes a long time to operate and is expensive to construct.
There has also been proposed an apparatus in which projections in the horizontal and vertical directions of two blocks are independently performed and motion vectors are detected independently in the horizontal and vertical directions. However, since the projection in the horizontal direction and the projection in the vertical direction are independently used in this proposed method, its motion vector detection precision is poor.
Therefore, an object of the present invention is to provide a method and apparatus for detecting motion vectors which avoids the aforementioned disadvantages of the prior art.
Another object of the present invention to detect motion vectors more efficiently without deteriorating detection precision.
Yet another object of the present invention is to detect motion vectors using a simplified circuit design.
A further object of the present invention is to reduce the amount of calculation required to detect a motion vector.
In accordance with an aspect of this invention, a method and apparatus for detecting motion vectors stores and reads out a reference block having a first size, and forms the read out reference block into a first set of small blocks. A search range having a second size as least as large as the first size is stored and a portion of the stored search range is read out as a check block having the first size in response to a control signal which indicates different portions of the stored search range. The read out check block is formed into a second set of small blocks which are compared with the first set of small blocks to determine which of the check blocks read out from the search range best matches the reference block, and a motion vector is produced between the reference block and the best matching check block.
The first and second sets of small blocks are formed in at least two directions. The small blocks formed from the read out reference block in a first direction are compared with the small blocks formed from the read out check block in the first direction. The small blocks formed from the read out reference block in a second direction are compared with the small blocks formed from the read out check block in the second direction.
At least one feature value is generated for each of the small blocks in the first and second sets of small blocks. The feature values for the first and second sets of small blocks are compared.
When the first and second sets of small blocks are formed in at least two directions, and at least one feature value is generated for each of the small blocks formed in each of a first and second direction, then the small blocks formed from the read out reference block in the first direction are compared with the small blocks formed from the read out check block in the first direction, and the small blocks formed from the read out reference block in the second direction are compared with the small blocks formed from the read out check block in the second direction.
Thus, the amount of calculation used in detecting a motion vector can be reduced without substantially deteriorating the detection precision of the motion vector.
In a multistep method according to the present invention, coarse portions of the search range respectively differing by at least two pixels are indicated, and a coarse motion vector is produced in response to the check blocks read out from the coarse portions of the search range. Fine portions of a subset of the search range respectively differing by one pixel are indicated, and a fine motion vector is produced in response to the check blocks read out from the fine portions of the subset of the search range.
In an interpolating method according to the present invention, the pixels read out of the stored search range are interpolated to form interpolated pixels which are formed into the second set of small blocks so that the motion vector has a resolution of higher than one pixel.
In accordance with another aspect of this invention, a method and apparatus for detecting motion vectors stores and reads out a reference block having a first size, and generates at least one first feature value representing the read out reference block. A search range having a second size at least as large as the first size is stored and a portion of the stored search range is read out as a check block having the first size in response to a control signal which indicates different portions of the stored search range. At least one second feature value representing the read out check block is generated and compared with the at least one first feature value to determine which of the check blocks read out from the search range best matches the reference block, and a motion vector is produced between the reference block and the best matching check block.
In accordance with another aspect of this invention, a method and apparatus for detecting motion vectors stores and reads out first and second reference blocks, and generates at least one first feature value and at least one second feature value representing the read out first and second reference blocks, respectively. First and second search ranges are stored and a portion of one of the first and second search ranges is read out and at least one third feature value representing the read out portion of the search ranges is generated. The at least one first and third feature values are compared, and a first motion vector is produced as a function of this comparison. The at least one second and third feature values are compared, and a second motion vector is produced as a function of this comparison.
The above, and other objects, features and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments of the present invention when read in conjunction with the accompanying drawings in which corresponding parts are identified by the same reference numeral.